package BinaryTree;

import java.util.LinkedList;

public class MyBinaryTree {

    //指向左子树
    private MyBinaryTree left;
    //当前节点的值
    private int val;
    //指向右子树
    private MyBinaryTree right;

    //构造方法一:带一个值的参数
    public MyBinaryTree(int val) {
        this.val = val;
    }

    //构造方法二:带三个参数
    public MyBinaryTree(MyBinaryTree left, int val, MyBinaryTree right) {
        this.left = left;
        this.val = val;
        this.right = right;
    }


    //使用递归实现前序遍历
    public void preTraversalRecursion(MyBinaryTree node) {
        if (node == null) {
            return;
        }
        System.out.print(node.val + " ");
        preTraversalRecursion(node.left);
        preTraversalRecursion(node.right);
    }

    //使用递归实现中序遍历
    public void middleTraversalRecursion(MyBinaryTree node) {

        if (node == null) {
            return;
        }

        middleTraversalRecursion(node.left);
        System.out.print(node.val + " ");
        middleTraversalRecursion(node.right);

    }

    //使用递归实现后续遍历
    public void postTraversalRecursion(MyBinaryTree node) {
        if (node == null) {
            return;
        }
        postTraversalRecursion(node.left);
        postTraversalRecursion(node.right);
        System.out.print(node.val + " ");
    }


    //非递归实现前序遍历
    public void preTraversal(MyBinaryTree node) {
        MyBinaryTree curr = node;
        LinkedList<MyBinaryTree> stack = new LinkedList<>();

        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                System.out.print(curr.val + " ");
                stack.push(curr);
                curr = curr.left;
            }else {
                MyBinaryTree tp = stack.pop();
                curr = tp.right;
            }
        }
        System.out.println();

    }

    //非递归实现中序遍历
    public void middleTraversal(MyBinaryTree node) {
        MyBinaryTree curr = node;
        LinkedList<MyBinaryTree> stack = new LinkedList<>();
        while ( curr != null || !stack.isEmpty()) {

            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }else  {
                MyBinaryTree tp = stack.pop();
                System.out.print(tp.val + " ");
                curr = tp.right;
            }
        }
        System.out.println();

    }


    //非递归实现后序遍历
    public void postTraversal(MyBinaryTree node) {
        MyBinaryTree crr = node;
        LinkedList<MyBinaryTree> stack = new LinkedList<>();
        MyBinaryTree pop = null;//最后一次弹栈元素
        while ( crr != null || !stack.isEmpty()) {
            if (crr != null) {
                stack.push(crr);
                crr = crr.left;
            }else {
                MyBinaryTree tp = stack.peek();
                if ( tp.right == null || tp.right == pop ) {
                    pop = stack.pop();
                    System.out.print(pop.val + " ");
                }else {
                    crr = tp.right;
                }

            }
        }
    }

}


